package leetcode.od;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author pppppp
 * @date 2022/5/9 9:14
 * <p>
 * 给一个数组{1,1,1, 1, 1, 1, 1, 1, 1, 2}
 * 分别代表着{2,4,8,16,32,64,128,256,512,1024}的个数，
 * 设计一个 算法 ，计算至少相加多少次能得到2048这个数字。
 */
public class 指定和最小个数 {

    @Test
    public void T_() {
        int[][] nums = {{0, 0, 1, 2, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 2}};
        int[] targets = {64, 2048,};
        int[] res = {3, 2};
        for (int i = 0; i < nums.length; i++) {
            // System.out.println(solution(nums[i], targets[i]) == res[i]);
            System.out.println(solution_(nums[i], targets[i]) == res[i]);
        }
    }

    /*01背包 降序排列 dp[i][j]  前i个最大和恰好等于j时 最小数量*/
    private int solution(int[] nums, int target) {
        int n = Arrays.stream(nums).sum();
        int[][] dp = new int[n][target + 1];
        int[] data = new int[n];
        int index = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            int num = nums[i];
            while (num > 0) {
                data[index++] = 1 << (i + 1);
                num--;
            }
        }
        Arrays.fill(dp[0], n + 1);
        dp[0][data[0]] = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= target; j++) {
                if (j > data[i]) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - data[i]] + 1);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][target];
    }

    /*空间优化*/
    private int solution_(int[] nums, int target) {
        int n = Arrays.stream(nums).sum();
        int[] dp = new int[target + 1];
        int[] data = new int[n];
        int index = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            int num = nums[i];
            while (num > 0) {
                data[index++] = 1 << (i + 1);
                num--;
            }
        }
        /*赋初始值*/
        Arrays.fill(dp, n + 1);
        dp[data[0]] = 1;

        for (int i = 1; i < n; i++) {
            for (int j = data[i]; j <= target; j++) {
                if (j > data[i]) {
                    dp[j] = Math.min(dp[j], dp[j - data[i]] + 1);
                }
            }
        }
        return dp[target];
    }
}
